class Solution {//leetcode143——重排两个链表
private:
    ListNode* reverse_list(ListNode*head){
        if(head==nullptr) return nullptr;
        ListNode*newhead=new ListNode;
        ListNode* next=head->next;
        while(head){
            head->next=newhead->next;
            newhead->next=head;
            head=next;
            if(head) next=head->next;
        }
        next=newhead->next;
        delete newhead;
        return next;
    }
    void push_back(ListNode*tail,ListNode*node){
        node->next=tail->next;
        tail->next=node;
    }
public:
    void reorderList(ListNode* head) {
        ListNode*newhead=new ListNode;//空节点
        //找到链表的中间节点
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            if(fast) slow=slow->next;
        }
        ListNode* mid=slow,*half_back=mid->next;
        mid->next=nullptr;
        //翻转链表
        half_back=reverse_list(half_back);
        //合并两个链表
        ListNode* tail=newhead;
        ListNode*cur1=head,*cur2=half_back;
        ListNode* next1=nullptr;
        ListNode* next2=nullptr;
        while(cur1||cur2){
            if(cur1) next1=cur1->next;
            if(cur2) next2=cur2->next;
            if(cur1) {//尾插cur1
                push_back(tail,cur1);
                tail=tail->next;
            }
            if(cur2){
                push_back(tail,cur2);
                tail=tail->next;
            }
            cur1=next1;
            cur2=next2;
        }
        delete newhead;
    }
};